//给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
//
//
//
// 示例 1：
//
//
//输入：s = "aaabb", k = 3
//输出：3
//解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
//
//
// 示例 2：
//
//
//输入：s = "ababbc", k = 2
//输出：5
//解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
//
//
//
// 提示：
//
//
// 1 <= s.length <= 104
// s 仅由小写英文字母组成
// 1 <= k <= 105
//
// Related Topics 哈希表 字符串 分治 滑动窗口
// 👍 505 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

public class LongestSubstringWithAtLeastKRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new LongestSubstringWithAtLeastKRepeatingCharacters().new Solution();
        solution.longestSubstring("aaabb",3);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 逆向思维，找不满足的点将字符串分割，重复该过程
        public int longestSubstring(String s, int k) {
            return dfs(s,0,s.length()-1,k);
        }

        private int dfs(String s, int start, int end, int k) {
            int[] map = new int[26];
            for (int l = start; l <= end; l++) {
                map[s.charAt(l)-'a']++;
            }

            char split = 0;
            for (int i = 0; i < map.length; i++) {
                if (map[i]>0 && map[i]<k){
                    split = (char) (i+'a');
                    break;
                }
            }
            if (split==0){
                return end-start+1;
            }

            int i=start;
            int res = 0;
            while (i<=end){
                while (i<=end && s.charAt(i)==split){
                    i++;
                }
                int newStart = i;
                if (i>end){
                    break;
                }
                while (i<=end && s.charAt(i)!=split){
                    i++;
                }
                res = Math.max(res,dfs(s,newStart,i-1,k));
            }
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}